• Cho tập A các ký hiệu và trọng số (tần suất) của chúng.
• Tìm một bộ mã tiền tố với tổng độ dài mã hóa là nhỏ nhất.

Dữ liệu

Bảng n {\displaystyle n} chữ cái A = { a 1 , a 2 , ⋯ , a n } {\displaystyle A=\left\{a_{1},a_{2},\cdots ,a_{n}\right\}} .
Tập các trọng số (tần suất xuất hiện) tương ứng W = { w 1 , w 2 , ⋯ , w n } {\displaystyle W=\left\{w_{1},w_{2},\cdots ,w_{n}\right\}} , ví dụ: w i = w e i g h t ( a i ) , 1 ≤ i ≤ n {\displaystyle w_{i}=\mathrm {weight} \left(a_{i}\right),1\leq i\leq n} .

Bộ mã C ( A , W ) = { c 1 , c 2 , ⋯ , c n } {\displaystyle C\left(A,W\right)=\left\{c_{1},c_{2},\cdots ,c_{n}\right\}} , là tập hợp các từ mã (codeword) (nhị phân), trong đó c i {\displaystyle c_{i}} là từ mã của a i , 1 ≤ i ≤ n {\displaystyle a_{i},1\leq i\leq n} .

Đặt L ( C ) = ∑ i = 1 n w i × l e n g t h ( c i ) {\displaystyle L\left(C\right)=\sum _{i=1}^{n}{w_{i}\times \mathrm {length} \left(c_{i}\right)}} là trọng số của bộ mã C {\displaystyle C} . Điều kiện là: L ( C ) ≤ L ( T ) {\displaystyle L\left(C\right)\leq L\left(T\right)} với mọi bộ mã T ( A , W ) {\displaystyle T\left(A,W\right)} .

Ví dụ

• Trong ví dụ sau, với các tần số như trên mã 1 sẽ tốn không gian hơn mã 2.